# 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
#
#  求在该柱状图中，能够勾勒出来的矩形的最大面积。
#
#  示例 1:
# 输入：heights = [2,1,5,6,2,3]
# 输出：10
# 解释：最大的矩形为图中红色区域，面积为 10
#
#
#  示例 2：
# 输入： heights = [2,4]
# 输出： 4
import math
from typing import List


class Rect:
    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height


class Solution:
    """
            单调栈写法二
            单调栈对暴力法进行优化
            暴力法求解每个高度对应的宽度时都是分别先前向后进行遍历
            优化思路：单调栈
                维护的是一个Rect.height 单调递增（栈底到栈顶方向单调递增）的栈，当单调递增栈的单调性被破坏的时候，
                说明之前栈顶（最高的柱子）能确定的最大面积就定了
            :param heights:
            :return:
            """

    def largestRectangleArea3(self, heights: List[int]) -> int:
        sigleStack = []  # 栈用于存储高度确定的矩形的最大面积
        res = 0
        heights += [0]  # 尾部添加一个 0 可以视为最后有一个高度为 0 的柱子，可以保证最后栈一定会被弹空
        for h in heights:
            accumulatedWidth = 0
            # 栈顶存储的高度 >= 当前的高度的时候，单调性（单调递增）被破坏，也就确定了栈顶高度的扩展范围
            # 此时需要计算一下这个高度能确定的最大矩形的面积，并尝试更新答案
            while len(sigleStack) and sigleStack[-1].height >= h:
                tmpRect = sigleStack.pop()
                accumulatedWidth += tmpRect.width
                res = max(res, tmpRect.height * accumulatedWidth)
            sigleStack.append(Rect(width=accumulatedWidth + 1, height=h))
        return res

    def largestRectangleArea2(self, heights: List[int]) -> int:
        """
        单调栈对暴力法进行优化
        暴力法求解每个高度对应的宽度时都是分别先前向后进行遍历
        优化思路：单调栈
            在枚举到第 i 根柱子的时候，就可以先把所有高度大于等于 height[i] 的 j 值全部移除，剩下的 j 值中高度最高的即为答案。
            在这之后，将 i 放入数据结构中，开始接下来的枚举
        :param heights:
        :return:
        """
        n, res = len(heights), 0
        lefts, rights, stack = [0] * n, [0] * n, []  # lefts[i]表示 heights[i] 的左边界，rights[i]表示 heights[i] 的右边界
        for i, h in enumerate(heights):  # 顺序遍历求每个宽度的左边界
            while stack and heights[stack[-1]] >= h:  # 把所有高度大于等于当前高度 h 的值全部移除
                stack.pop()
            lefts[i] = stack[-1] if stack else -1  # 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的左边界为 -1(哨兵)
            stack.append(i)

        stack.clear()
        for i in range(n - 1, -1, -1):  # 倒序遍历求每个宽度的右边界
            while stack and heights[stack[-1]] >= heights[i]:  # 把所有高度大于等于当前高度 h 的值全部移除
                stack.pop()
            rights[i] = stack[-1] if stack else n  # 特殊情况是栈中所有的值都比当前height[i]大，该元素宽度的右边界为 n(哨兵)
            stack.append(i)

        for i, h in enumerate(heights):
            res = max(res, h * (rights[i] - lefts[i] - 1))
        return res

    def largestRectangleArea1(self, heights: List[int]) -> int:
        """
        暴力法（超时）
        枚举所有可能的高，然后求出每个高所对应的最大宽
        :param heights:
        :return:
        """
        res, n = 0, len(heights)
        for i, h in enumerate(heights):  # 枚举所有可能的高，求当前高所对应的最大宽
            left, right = i - 1, i + 1
            while left >= 0 and heights[left] >= h:  # 向前寻找当前宽的左边界
                left -= 1
            while right < n and heights[right] >= h:  # 向后寻找当前宽的右边界
                right += 1
            res = max(res, h * (right - left - 1))  # 尝试更新结果
        return res

    def largestRectangleArea(self, heights: List[int]) -> int:
        return self.largestRectangleArea3(heights)


if __name__ == '__main__':
    heights = [2, 1, 5, 6, 2, 3]
    print(Solution().largestRectangleArea(heights))
